package com.zhj.leetcode;

/**
 * 力扣53 最大子序和
 * @author zhj
 */
public class Test53 {
    public static void main(String[] args) {
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(getSonMax(nums));
        System.out.println(dp(nums));
    }

    private static int dp(int[] nums) {
        int pre = 0;
        int max = nums[0];
        for (int num : nums) {
           pre = Math.max(num, pre + num);
           max = Math.max(max, pre);
        }
        return max;
    }

    private static int getSonMax(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        return getMax(nums, 0, nums.length-1);
    }

    private static int getMax(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        int mid = left + (right - left) / 2;
        int leftMax = getMax(nums, left, mid);
        int rightMax = getMax(nums, mid+1, right);
        int crossMax = getCrossMax(nums, left, right);
        return Math.max(Math.max(leftMax,rightMax),crossMax);
    }

    private static int getCrossMax(int[] nums, int left, int right) {
        int mid = left + (right - left) / 2;
        int leftSum = nums[mid];
        int leftMax = leftSum;
        for (int i = mid-1; i > left; i--) {
            leftSum = leftSum + nums[i];
            leftMax = Math.max(leftMax, leftSum);
        }
        int rightSum = nums[mid+1];
        int rightMax = rightSum;
        for (int i = mid+2; i < right; i++) {
            rightSum = rightSum + nums[i];
            rightMax = Math.max(rightMax, rightSum);
        }
        return leftMax + rightMax;
    }
}
